In a multi-processor system having multiple processors and multiple caches, each cache may store a copy of a piece of data stored in memory. Problems arise when more than one cache contains a copy of the same piece of data. Various techniques have been developed to ensure data coherency across multiple caches. For example, when the data in one cache is modified, other copies of the data are marked as invalid so that they will not be used.
To help maintain cache coherency, many systems include a directory such as a snoop filter to aid in determining presence and state of data in cache lines of such multiple caches. A snoop operation can take place in which an agent of a bus monitors memory transactions, e.g., read/write operations. The agent may record the states of the cache lines involved in the memory transactions in the snoop filter. The state of a cache line may indicate whether the line has only one valid copy outside of the main memory, has multiple valid copies shared by multiple caches, or has no copies outside of main memory (i.e., it has been invalidated in all caches). A data entry in the snoop filter is often indexed in part by a portion of its address in the main memory.
The snoop filter sometimes may run out of space to record the state of a line for a new memory transaction, and may need to evict an entry from the snoop filter to accommodate the new transaction. Often when an entry is evicted from the snoop filter, a back-invalidation message is sent to every processor cache that potentially holds a valid copy of the line associated with the evicted entry. Many cache misses are due to snoop filter originated back invalidations of a cache line that was about to be used.
Some snoop filters are referred to as inclusive snoop filters (ISFs), in that the information in the snoop filter is maintained inclusively with cache lines of the caches that the snoop filter covers. In an inclusive cache hierarchy, one of the cache memories (i.e., a lower-level cache memory) includes a subset of data contained in another cache memory (i.e., an upper-level cache memory). Cache hierarchies may improve processor performance, as they allow a smaller cache having a relatively fast access speed to contain frequently used data. In turn, a larger cache having a slower access speed than the smaller cache stores less-frequently used data (as well as copies of the data in the lower-level cache).
Snoop filters, as with the caches they cover, allocate and evict entries. However, because an inclusive cache hierarchy with an ISF stores some common data, eviction of a cache line in one cache level or snoop filter may cause a corresponding cache line eviction in another level of the cache hierarchy to maintain cache coherency. ISFs must insure that a cache line whose address is evicted from the snoop filter be removed from all covered caches. In general, this involves sending a back invalidation request from the snoop filter to the covered caches. When the snoop filter sends many such requests, it consumes interconnect bandwidth that can increase effective memory latency, as well as potentially removing useful cache entries.